/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function (matrix) {
  // 获取矩阵的行数和列数
  const m = matrix.length;
  const n = matrix[0].length;

  // 初始化dp矩阵，与原矩阵大小相同
  const dp = new Array(m);
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }

  let count = 0;

  // 填充第一行
  for (let j = 0; j < n; j++) {
    dp[0][j] = matrix[0][j];
    count += dp[0][j];
  }

  // 填充第一列
  for (let i = 1; i < m; i++) {
    dp[i][0] = matrix[i][0];
    count += dp[i][0];
  }

  // 填充dp矩阵的其他部分
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 如果当前位置是1，则可以构成正方形
      if (matrix[i][j] === 1) {
        // 当前位置的最大正方形边长由左上、上、左三个位置决定
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
      } else {
        dp[i][j] = 0;
      }
      // 累加正方形数量
      count += dp[i][j];
    }
  }

  return count;
};

// 测试案例
console.log(
  countSquares([
    [0, 1, 1, 1],
    [1, 1, 1, 1],
    [0, 1, 1, 1],
  ])
); // 输出: 15

console.log(
  countSquares([
    [1, 0, 1],
    [1, 1, 0],
    [1, 1, 0],
  ])
); // 输出: 7
